package ljl.alg.wangzheng_camp.round1.dp;

import commons.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 这是我能做出来的题吗？
 * */
public class _337_rob {
    
    /**
     * 思路是：node 可以选或不选，如果选：node.val + noChoose.get(node.left) + noChoose.get(node.right)
     * 如果不选，左右孩子并不是非得选，是可选可不选 max(choose.get(node.left), noChoose.get(node.left)) + ...(right)
     * */
    static class fg {
        Map<TreeNode, Integer> choose = new HashMap<>();
        Map<TreeNode, Integer> noChoose = new HashMap<>();
        
        public int rob(TreeNode root) {
            dfs(root);
            return Math.max(choose.get(root), noChoose.get(root));
        }
        void dfs(TreeNode node) {
            if (node == null)
                return;
            dfs(node.left);
            dfs(node.right);
            choose.put(node, node.val + noChoose.getOrDefault(node.left, 0) + noChoose.getOrDefault(node.right, 0));
            noChoose.put(node, Math.max(choose.getOrDefault(node.left, 0), noChoose.getOrDefault(node.left, 0)) +
                Math.max(choose.getOrDefault(node.right, 0), noChoose.getOrDefault(node.right, 0)));
        }
    }
    
    static class optimized_fg {
        public int rob(TreeNode root) {
            int[] chooseOrNot = dfs(root);
            return Math.max(chooseOrNot[0], chooseOrNot[1]);
        }
        int[] dfs(TreeNode root) {
            if (root == null) return new int[] {0, 0};
            int[] left = dfs(root.left), right = dfs(root.right);
            int choose = root.val + left[1] + right[1], orNot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            return new int[]{choose, orNot};
        }
    }
    
}
